DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2024.57

Shortest Two Disjoint Paths in Conservative Graphs

Authors: Ildikó Schlotter

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract

We consider the following problem that we call the Shortest Two Disjoint Paths problem: given an undirected graph G = (V,E) with edge weights w:E → ℝ, two terminals s and t in G, find two internally vertex-disjoint paths between s and t with minimum total weight. As shown recently by Schlotter and Sebő (2022), this problem becomes NP-hard if edges can have negative weights, even if the weight function is conservative, i.e., there are no cycles in G with negative total weight. We propose a polynomial-time algorithm that solves the Shortest Two Disjoint Paths problem for conservative weights in the case when the negative-weight edges form a constant number of trees in G.

Cite as

Ildikó Schlotter. Shortest Two Disjoint Paths in Conservative Graphs. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 57:1-57:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{schlotter:LIPIcs.STACS.2024.57,
  author =	{Schlotter, Ildik\'{o}},
  title =	{{Shortest Two Disjoint Paths in Conservative Graphs}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{57:1--57:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.57},
  URN =		{urn:nbn:de:0030-drops-197678},
  doi =		{10.4230/LIPIcs.STACS.2024.57},
  annote =	{Keywords: Shortest paths, disjoint paths, conservative weights, graph algorithm}
}

Search Results

Documents authored by Schlotter, Ildikó

Shortest Two Disjoint Paths in Conservative Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message